package text_2023_10_07;

/**
 * @author Vv
 * @version 1.0
 * @project coding_learn
 * @description
 * @date 2023/10/9 10:15:11
 */
public class StickersToSpellWord {
    public static int minStrickers(String[] stickers,String target){
        int ans = process1(stickers,target);
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
    private static int process1(String[] stickers,String target){
        if(target.length() == 0){
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for(String first : stickers){
            String rest = minus(first,target);
            if(rest.length() != target.length()){
                min = Math.min(min,process1(stickers,rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }
    private static String minus(String first,String target){
        char[] str1 = first.toCharArray();
        char[] str2 = target.toCharArray();
        int[] count = new int[26];
        for(char chars : str1){
            count[chars]--;
        }
        for(char chars : str2){
            count[chars] ++ ;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0;i<count.length;i++){
            if(count[i] > 0){
               for(int j = 0;j<count[i];j++){
                   stringBuilder.append((char)(i + 'a'));
               }
            }
        }
        return stringBuilder.toString();
    }
}
